% !TEX TS-program = pdflatex
\documentclass[10pt, a4paper]{article}

\usepackage{a4wide}
\usepackage{color}
\usepackage{amsmath,amssymb,epsfig,pstricks,xspace}
\usepackage{german,graphics}
\usepackage{dsfont}
\usepackage{amsfonts}
\usepackage{graphics, psfrag}
\usepackage[latin1]{inputenc}
\usepackage[T1]{fontenc}
\usepackage{enumitem} 
\usepackage{url}
\usepackage{array,dcolumn,booktabs}
\usepackage{pdflscape}
\usepackage{amsthm}
\usepackage{listings}
\usepackage{graphicx} 
\usepackage[section]{placeins}
\usepackage{longtable}


\usepackage{pifont}

\newcommand{\header}{
  \begin{center}
  \fbox{\parbox{11cm}{
    \begin{center}
      {\Large Lab 6 -- Solution\\ \vspace{0.2em}
        {\bf Search Algorithms}\\ \vspace{0.7em} (Winter Term 2014/2015)\\
        \vspace{0.2em} \firstnameone \lastnameone\\
        \vspace{0.2em} \matriculationnumberone\\
        \vspace{0.2em} \firstnametwo \lastnametwo\\
        \vspace{0.2em} \matriculationnumbertwo\\
        \vspace{0.2em} \firstnamethree \lastnamethree\\
        \vspace{0.2em} \matriculationnumberthree
    }
    \end{center}
  }}
  \end{center}
}


%-------------------------------------------------------------------------------
%---------------------------- EDIT FROM HERE -----------------------------------
%-------------------------------------------------------------------------------

\newcommand{\firstnameone}{Jiaqi	}
\newcommand{\lastnameone}{Weng}
\newcommand{\matriculationnumberone}{115131}

\newcommand{\firstnametwo}{Vasilii	}
\newcommand{\lastnametwo}{Ponteleev}
\newcommand{\matriculationnumbertwo}{115151}

\newcommand{\firstnamethree}{Le Do Thai	}
\newcommand{\lastnamethree}{Binh   }
\newcommand{\matriculationnumberthree}{114910}

\begin{document}
\pagestyle{plain}
\header


\textbf{Task 1}\\
a) when the goal node change.\\\\
b) when another parent node n' of n expend and  g(n')+c(n,n') < g(n).\\\\
c) Don't know if there any particuluar difference from b).\\\\
d) Since nodes will not be expanded again (h is monotonic), g(n) is calculated only once during the first expansion.
\\\\
\textbf{Task 2}\\
no, because algorithm Z is not Delayed termination, when the algorithm get goal node, return it directly, not check it is admissible or not.\\
\\
\textbf{Task 3}\\
a)\\
h(n)<= c(n, n') + h(n')\\
dm(n1,n2)/3 <= c(n1,n') + dm(n',n2)/3\\
b)\\
show monotone,\\
dm(n1,n2)/3 <= c(n1,n') + dm(n',n2)/3\\
dm(n1,n2) - 3 <= dm(n',n2)<= dm(n1,n2) + 3\\
so, we can see dm(n1,n2)/3 <= (c(n1,n') +/- 1)+ dm(n1,n2)/3\\
because c(n1,n') >= 1\\
show admissible,\\
the max of distance between node and its parent node is 3,\\
assume there is n nodes between start and end as C*.\\
we can get value of dm(s,r) <= 3n.\\
h(s) = dm(s,r)/3 <= n <= C*\\
so we can say h(n) is admissible.\\
c)\\
$h(n)=line^2/16$ (max line = 8)\\
$h(a)=8^2/16=4$\\
$h(b)=6^2/16=2$\\
h(a)>1+h(b)\\
\\
\textbf{Task 5}\\
Nodes estimated to be closer to a goal node are preferred.\\
\\
\textbf{Task 7}\\\\
a) DWA* emphasizes depth-first component at the start. So, if we cannot reach the solution depth-first component won't do us any ggod. However, I can't be absolutely sure about anything when I don't have parameters N and $\epsilon$. I think they really matters.\\\\
b) $f_{d \epsilon}(n) = g(n) + (1 + (1 - {{min(depth(n),N)} \over {N}}) \cdot \epsilon) \cdot h(n)$\\\\
Since $h(n) \approx h^{*}(n)$, $\epsilon \approx 1$, $N = 1$\\\\\
$f_{d \epsilon}(n) = g(n) + (1 + (1 - depth(n))) \cdot h^{*}(n)$\\\\
The deeper we go, the cheaper we get. The number of nodes expansions will increase dramatically. \\\\
c) $f_{d \epsilon}(n) = g(n) + (1 + (1 - {{min(depth(n),N)} \over {N}}) \cdot \epsilon) \cdot h(n)$\\\\
$\lim_{N\to\infty} f_{d \epsilon}(n)$  =  $g(n) + (1 + \epsilon) \cdot h(n)$\\\\
Since $h(n) \approx h^{*}(n)$, $\epsilon \approx 1$\\\\\
$f_{d \epsilon}(n) \approx g(n) + 2 \cdot h^{*}(n)$\\\\
Which means we'll perfom better.\\\\ 
d) You wil find implementation in eight puzzle archive. It's IntelliJ IDEA https://www.jetbrains.com/idea/ project, requires Java 8 to be built. To estimate performance just run unit tests from test submodule. To save the time and because I'm lazy, I didn't add build support (Gradle or at least Ant), so you have to use IntelliJ IDEA. Unit tests are also not quite clean (because one test covers too much), but I intend to leave it be. \\\\
e, f) See last page.\\\\
g) Optimal solution 31 moves can be achieved with $\epsilon = 1$ and $N \in 35...50$. \\\\
h) The smallest node expansions 90 is achieved with $\epsilon = 2$ and $N = 35$, but we have 45 moves, the highest value of all.\\\\
% Please add the following required packages to your document preamble:
% \usepackage{booktabs}
\begin{table}[h]
\begin{tabular}{@{}cccc@{}}
\toprule
\textbf{N}           & \textbf{Epsilon}     & \textbf{Expansions}  & \textbf{Moves}       \\ \midrule
\multicolumn{1}{l}{} & \multicolumn{1}{l}{} & \multicolumn{1}{l}{} & \multicolumn{1}{l}{} \\
5                    & 0.125                & 8224                 & 31                   \\
10                   & 0.125                & 7956                 & 31                   \\
15                   & 0.125                & 10294                & 31                   \\
20                   & 0.125                & 3714                 & 31                   \\
25                   & 0.125                & 3620                 & 31                   \\
30                   & 0.125                & 7570                 & 31                   \\
35                   & 0.125                & 7570                 & 31                   \\
40                   & 0.125                & 7570                 & 31                   \\
45                   & 0.125                & 7570                 & 31                   \\
50                   & 0.125                & 7570                 & 31                   \\
                     &                      &                      &                      \\
5                    & 0.25                 & 8367                 & 31                   \\
10                   & 0.25                 & 2849                 & 31                   \\
15                   & 0.25                 & 2252                 & 31                   \\
20                   & 0.25                 & 1062                 & 31                   \\
25                   & 0.25                 & 3106                 & 31                   \\
30                   & 0.25                 & 4061                 & 31                   \\
35                   & 0.25                 & 3918                 & 31                   \\
40                   & 0.25                 & 3918                 & 31                   \\
45                   & 0.25                 & 3918                 & 31                   \\
50                   & 0.25                 & 3918                 & 31                   \\
                     &                      &                      &                      \\
5                    & 0.5                  & 2002                 & 31                   \\
10                   & 0.5                  & 452                  & 31                   \\
15                   & 0.5                  & 412                  & 31                   \\
20                   & 0.5                  & 380                  & 31                   \\
25                   & 0.5                  & 984                  & 31                   \\
30                   & 0.5                  & 482                  & 31                   \\
35                   & 0.5                  & 482                  & 31                   \\
40                   & 0.5                  & 482                  & 31                   \\
45                   & 0.5                  & 482                  & 31                   \\
50                   & 0.5                  & 482                  & 31                   \\
                     &                      &                      &                      \\
5                    & 1.0                  & 2002                 & 31                   \\
10                   & 1.0                  & 452                  & 31                   \\
15                   & 1.0                  & 583                  & 35                   \\
20                   & 1.0                  & 147                  & 35                   \\
25                   & 1.0                  & 965                  & 39                   \\
30                   & 1.0                  & 241                  & 39                   \\
\textbf{35}          & \textbf{1.0}         & \textbf{349}         & \textbf{31}          \\
\textbf{40}          & \textbf{1.0}         & \textbf{349}         & \textbf{31}          \\
\textbf{45}          & \textbf{1.0}         & \textbf{349}         & \textbf{31}          \\
\textbf{50}          & \textbf{1.0}         & \textbf{349}         & \textbf{31}          \\
                     &                      &                      &                      \\
5                    & 2.0                  & 2002                 & 31                   \\
10                   & 2.0                  & 452                  & 31                   \\
15                   & 2.0                  & 583                  & 35                   \\
20                   & 2.0                  & 147                  & 35                   \\
25                   & 2.0                  & 667                  & 43                   \\
30                   & 2.0                  & 254                  & 45                   \\
\textbf{35}          & \textbf{2.0}         & \textbf{90}          & \textbf{45}          \\
40                   & 2.0                  & 660                  & 39                   \\
45                   & 2.0                  & 555                  & 39                   \\
50                   & 2.0                  & 555                  & 39                   \\ \bottomrule
\end{tabular}
\end{table}


\end{document}
